package com.leecode;

/**
 * 234. 回文链表
 * <p>
 * 请判断一个链表是否为回文链表。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 1->2
 * 输出: false
 * <p>
 * 示例 2:
 * <p>
 * 输入: 1->2->2->1
 * 输出: true
 * <p>
 * 进阶：
 * 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
 */
public class Leet234 {
	public static void main(String[] args) {
//		new Leet234().isPalindrome(new ListNode(1, new ListNode(0,new ListNode(1))));
		new Leet234().isPalindrome(new ListNode(1, new ListNode(2)));
	}

	/**
	 * 我:第一遍O(n)到最后;第二遍双指针比较.但是指针走到未尾不能回退,比较个锤子
	 * 100%,97%,因为只有next,没有pre,高手用next造出"pre"的效果,有种类似"位运算代替+-*"的感觉
	 * 考点:由于这几个指针共用一个ListNode,修改操作最好尽量放在最后,不然会出bug!!
	 * 考点2:2节点,3节点边界条件
	 */
	public boolean isPalindrome(ListNode head) {
		if (head == null || head.next == null) return true;
		ListNode s = head;//由于不能
		ListNode q = head;
		ListNode revert = head;
		ListNode revertAft = null;
		while (q != null && q.next != null) {
			q = q.next.next;//
			revert = s;
//			revert.next = revertAft;//修改操作
			s = s.next;//往后移可以,但revert需要反转第一个节点,s后移,已经是第二个节点了,所以提前把s做备份
			revert.next = revertAft;//修改操作
			//			revert.next=null;//翻转第一个节点,它后面是null没错,但翻转第二个节点的时候,第二个节点后面是第一个节点而不是null
			revertAft = revert;

		}

		boolean flag = true;
		while (flag) {
			if (s == null && revert != null) return false;
			if (revert == null && s != null) return false;
			if (revert == null && s == null) return true;
			if (s.val != revert.val) return false;
			s = s.next;
			revert = revert.next;
		}
		return true;
	}

	public boolean isPalindrome2(ListNode head) {
		if (head == null || head.next == null) {
			return true;
		}
		ListNode slow = head, fast = head;
		ListNode pre = head, prepre = null;
		while (fast != null && fast.next != null) {
			pre = slow;//?????????slow后移,pre不受影响???
			slow = slow.next;//?????????slow后移,pre不受影响???
			fast = fast.next.next;
			pre.next = prepre;
			prepre = pre;
		}
		if (fast != null) {//3个节点的时候,就会发现这么妙的么?!!!!!!!!!!!!!!
			slow = slow.next;
		}
		while (pre != null && slow != null) {
			if (pre.val != slow.val) {
				return false;
			}
			pre = pre.next;
			slow = slow.next;
		}
		return true;
	}

}
